У ово време глобалне епидемије вируса, наш познати научник Милош је, као једини довољно квалификовани научник за овај посао, добио задатак да анализира генетичку структуру вируса у својој лабараторији. Ако његова анализа буде успешна, она ће загарантовати проналажење лека и ослобођење света од вируса.

Генетичка структура вируса \(G\) се може представити као пермутација бројева од \(1\) до \(N\), то јест, низ бројева од \(1\) до \(N\) дужине \(N\) где се сваки број појављује тачно једном.

Како би Милош могао да уради своју анализу, генетичка структура мора да буде сортирана. За соритрање генетичке структуре Милош користи веома специјалну машину. Ова машина му дозвољава да узме неки сегмент низа и обрне га. Тачније, може да одабере два индекса \(l\) и \(r\) тако да важи \(l\leq r\), и обрне подниз од \(l\)-те до \(r\)-те позиције у низу (замени места елементима \(G_l\) i \(G_r\), \(G_{l+1}\) i \(G_{r-1}\), \(\ldots\) ). Милош такође зна да су гени веома осетљиви и да ће се оштетити ако употреби машину више пута на исти ген (Милош може да употреби машину произвољан број пута, али интервали индекса које одабере морају бити дисјунктни.)

Како Милош нема искуства са коришћењем ове машине, потребна му је ваша помоћ! Кажите му да ли је могуће уз помоћ ове машине сортирати генетичку структуру без оштећења гена или не. Ако је сортирање генетичке структуре могуће, такође му је потребна и секвенца операција коју треба применити ради успешног сортирања. Због тога што је машина спора, а Милош хоће да лек буде готов што пре, потребно је и да секвенца операција буде најкраћа могућа (уколико постоји више најкраћих секвенци, исписати било коју).

Опис улаза

Прва линија стандардног улаза садржи број \(N\), дужину генетичке структуре. Друга линија стандардног улаза садржи низ \(G\), генетичку структуру.

Опис излаза

Уколико је сортирање генетичке структуре могуће, у првој линији стандардног излаза исписати “Svet je spasen”, у другој линији стандардног излаза исписати дужину најкраће могуће секвенце операција \(K\). У свакој од наредних \(K\) линија исписати два броја \(l_i\) и \(r_i\), индексе које Милош треба да одабере за \(i\)-ту операцију. Уколико сортирање генетичке структуре није могуће, у првој и јединој линији стандардног излаза исписати “Nema spasa”.

Пример 1

Улаз

8
2 1 4 3 5 6 7 8

Излаз

Svet je spasen
2
1 2
3 4

Пример 2

Улаз

8
1 6 7 3 2 5 4 8

Излаз

Nema spasa

Ограничења

• \(1\leq N\leq10^6\)
• \(1\leq G_i\leq N\)
• Сваки број од \(1\) до \(N\) се појављује тачно једном у \(G\).

Тест примери су подељени у 5 подзадатка: - [10 поена]: \(N \leq 3\), - [20 поена]: \(N \leq 20\), - [30 поена]: Ако постоји, најкраћа секвенца операција је дужине \(0\) или \(1\), \(N \leq 500\), - [20 поена]: \(N \leq 500\), - [20 поена]: Нема додатних ограничења.